{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Nice Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计「优美子数组」"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> 和一个整数 <code>k</code>。如果某个连续子数组中恰好有 <code>k</code> 个奇数数字，我们就认为这个子数组是「<strong>优美子数组</strong>」。</p>\n",
    "\n",
    "<p>请返回这个数组中 <strong>「优美子数组」</strong> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2,1,1], k = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,6], k = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数列中不包含任何奇数，所以不存在优美子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,2,1,2,2,1,2,2,2], k = 2\n",
    "<strong>输出：</strong>16\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 50000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-nice-subarrays](https://leetcode.cn/problems/count-number-of-nice-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-nice-subarrays](https://leetcode.cn/problems/count-number-of-nice-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,1,1]\\n3', '[2,4,6]\\n1', '[2,2,2,1,2,2,1,2,2,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        def atmost(k):\n",
    "            res=i=0\n",
    "            for j in range(len(nums)):\n",
    "                k -=nums[j]%2\n",
    "                while k <0:\n",
    "                    k+=nums[i]%2\n",
    "                    i+=1\n",
    "                res +=j-i+1\n",
    "            return res\n",
    "        return atmost(k)-atmost(k-1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n < k: return 0\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 1:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        res = 0\n",
    "        presum = 0\n",
    "        dic = {0:1}\n",
    "        for i in range(n):\n",
    "            presum += nums[i]\n",
    "            if presum-k in dic.keys():\n",
    "                res += dic[presum-k]\n",
    "            if presum not in dic.keys():\n",
    "                dic[presum] = 1\n",
    "            else:\n",
    "                dic[presum] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        for i in range(N):\n",
    "            nums[i] = nums[i]%2\n",
    "        sums = 0\n",
    "        mp = list=[0 for x in range(0,N+2)]\n",
    "        mp[0] = 1\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                sums += 1\n",
    "            mp[sums] += 1\n",
    "            if sums - k >= 0:\n",
    "                ans += mp[sums-k]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        dp = [0 for i in range(l+1)]\n",
    "        count = 0\n",
    "        ct = [0 for i in range(l+1)]\n",
    "        ct[0]=1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(l):\n",
    "            if nums[i] %2==1:\n",
    "                count += 1\n",
    "            dp[i+1]= count\n",
    "            ct[count] += 1\n",
    "            if count>=k:\n",
    "                ans +=  ct[count-k]\n",
    "\n",
    "        #print(dp)\n",
    "        #print(ct)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] %2 == 0:\n",
    "                nums[i] = 0\n",
    "            else:\n",
    "                nums[i] = 1\n",
    "        dic = {0:1}\n",
    "        sum1 = 0\n",
    "        res = 0\n",
    "        for each in nums:\n",
    "            sum1 += each \n",
    "            if sum1-k in dic:\n",
    "                res += dic[sum1-k]\n",
    "            if sum1 in dic:\n",
    "                dic[sum1] += 1\n",
    "            else:\n",
    "                dic[sum1] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 2 == 1:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        \n",
    "        # 前缀和 + 哈希字典\n",
    "        res = 0\n",
    "        summ = 0\n",
    "        dic = {}\n",
    "        dic[0] = 1  # 当出现summ-k==0时，res需要+1\n",
    "        for i in range(len(nums)):\n",
    "            summ += nums[i]\n",
    "            if summ-k in dic.keys():\n",
    "                res += dic[summ-k]\n",
    "            if summ not in dic.keys():\n",
    "                dic[summ] = 1\n",
    "            else:\n",
    "                dic[summ] += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        count = [0]*(len(nums)+1)\n",
    "        count[0] = 1\n",
    "        odd = ans = 0\n",
    "        for num in nums:\n",
    "            if num%2 == 1:\n",
    "                odd += 1\n",
    "            if odd >= k:\n",
    "                ans += count[odd - k]\n",
    "            count[odd] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        odd = [-1]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 1:\n",
    "                odd.append(i)\n",
    "        odd.append(n)\n",
    "        print(odd)\n",
    "        for i in range(1, len(odd) - k):\n",
    "            ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "            6/23: 第一次做思路：暴力解题，A[i, j], if i<=z<=j, and z%2==0, k+=1\n",
    "        \"\"\"\n",
    "        # nums = [1, 1, 2, 1, 1]  # 取2的模（%）\n",
    "        # nums = [1, 1, 0, 1, 1]  # 只有1和0\n",
    "        # 把统计k的奇数，变成了统计子段和是k\n",
    "        nums_copy = nums\n",
    "        nums = [i%2 for i in nums]\n",
    "        nums = [0] + nums\n",
    "        s = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            s[i] = s[i-1] + nums[i]\n",
    "\n",
    "        # 先把r,l两个循环变量分离。\n",
    "        # for r = 1 ~ n:\n",
    "        #     for l = 1 ~ r: # 取 [l,r]这个子段\n",
    "        #         if s[r] - s[l-1] == k:\n",
    "        #             ans+=1\n",
    "\n",
    "        # 先固定外层循环变量，考虑内存满足什么条件\n",
    "        # 考虑数学模型 ==> 对于每个r(1~n),考虑有几个l(1~r),能使得s[r]-s[l-1]=k     \n",
    "         \n",
    "        # 实现上的优化(or 问题的转化):\n",
    "        # 对于每个r(1~n),考虑有几个l(0~r-1),能使得s[r]-s[l]=k  \n",
    "        #                                         i    j \n",
    "        # 对于每个i(1~n),考虑有几个j(0~i-1),能使得s[i]-s[j]=k  \n",
    "        # 对于每个i(1~n),考虑有几个j(0~i-1),能使得s[j]=s[i]-k\n",
    "        # 即，在一个数组（s）中统计“等于某个数\"的数的数量，e.g., \n",
    "        # nums = [0, 1, 2, 3] ==> [0, 1, 0, 1] ==> Output is 2\n",
    "        # s = [0, 1, 1, 2]\n",
    "        # count = [1, 1, 2]\n",
    "        # 1个0，1个1，1个2\n",
    "\n",
    "        count = [0] * len(s)\n",
    "        for i in range(0, len(s)):  # for i = 0 ~ n\n",
    "            count[s[i]]+=1 \n",
    "\n",
    "        # 对于每个i(1~n),考虑有几个j(0~i-1),能使得s[j]=s[i]-k\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)): # for i = \n",
    "            if s[i]-k >=0:\n",
    "                ans+=count[s[i]-k]\n",
    "\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        odd = [-1]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num % 2:\n",
    "                odd.append(i)\n",
    "        odd.append(n)\n",
    "        ret = 0\n",
    "        m = len(odd)\n",
    "        for i in range(1, m - k):\n",
    "            ret += (odd[i] - odd[i-1]) * (odd[i+k] - odd[i+k-1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        cnt = 1\n",
    "        odd_list = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num % 2:\n",
    "                nums[idx] = 1\n",
    "                odd_list.append(cnt)\n",
    "                cnt = 1\n",
    "            else:\n",
    "                nums[idx] = 0\n",
    "                cnt += 1\n",
    "        odd_list.append(cnt)\n",
    "        rst = 0\n",
    "        for idx, val in enumerate(odd_list[:-k]):\n",
    "            rst += odd_list[idx]*odd_list[idx+k]\n",
    "        print(rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 将数组中奇数改为1，偶数改为0\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 1:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        pre = [0] * n\n",
    "        # 前缀和\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                pre[i] = nums[i]\n",
    "            else:\n",
    "                pre[i] = pre[i - 1] + nums[i]\n",
    "        ma = collections.defaultdict(int)\n",
    "        ma[0] = 1\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        for c in nums:\n",
    "            total += c\n",
    "            if total - k in ma:\n",
    "                ans += ma[total - k]\n",
    "            ma[total] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dict = {0:1}\n",
    "        presum = 0\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            nums[i] = nums[i] % 2\n",
    "            presum += nums[i]\n",
    "            if presum-k in dict:\n",
    "                count += dict[presum-k]\n",
    "\n",
    "            if presum in dict:\n",
    "                dict[presum] += 1\n",
    "            else:\n",
    "                dict[presum] = 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i, num in enumerate(nums):\n",
    "            if num % 2 == 1:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        right_start, right_end, n = -1, -1, len(nums) # [right_start, right_end]\n",
    "        odd_count = 0\n",
    "        ans = 0\n",
    "        for left in range(n):\n",
    "            if left >= 1:\n",
    "                odd_count -= nums[left-1]\n",
    "            while odd_count < k:\n",
    "                right_start += 1\n",
    "                if right_start == n: return ans\n",
    "                odd_count += nums[right_start]\n",
    "            right_end = right_start\n",
    "            while right_end+1 <= n-1 and nums[right_end+1] == 0:\n",
    "                right_end += 1\n",
    "            ans += right_end-right_start+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 2 == 1:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 0\n",
    "\n",
    "        res = 0\n",
    "        summ = 0\n",
    "        dic = {}\n",
    "        dic[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            summ += nums[i]\n",
    "            if summ - k in dic.keys():\n",
    "                res += dic[summ - k]\n",
    "            if summ not in dic.keys():\n",
    "                dic[summ] = 1\n",
    "            else:\n",
    "                dic[summ] += 1\n",
    "        return res                \n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums[i] % 2\n",
    "          \n",
    "        count = 0 \n",
    "        prefix_sum = 0  \n",
    "        prefix_sum_count = {0: 1}  \n",
    "\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum - k in prefix_sum_count:\n",
    "                count += prefix_sum_count[prefix_sum - k]\n",
    "            if prefix_sum in prefix_sum_count:\n",
    "                prefix_sum_count[prefix_sum] += 1\n",
    "            else:\n",
    "                prefix_sum_count[prefix_sum] = 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        count = 0\n",
    "        startleft = left\n",
    "        res = 0\n",
    "\n",
    "        while right<len(nums):\n",
    "            if nums[right]&1:\n",
    "                count += 1\n",
    "            right += 1\n",
    "\n",
    "            while count>k:\n",
    "                if nums[left]&1:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "                startleft = left\n",
    "            \n",
    "            while startleft<right and not(nums[startleft]&1):\n",
    "                startleft += 1\n",
    "            \n",
    "            if count == k:\n",
    "                res += startleft-left+1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        newnums=[0]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%2==1:\n",
    "                newnums.append(i+1)\n",
    "        newnums.append(len(nums)+1)\n",
    "        for i in range(1,len(newnums)-k):\n",
    "            ans+=(newnums[i]-newnums[i-1])*(newnums[i+k]-newnums[i+k-1])\n",
    "        return ans\n",
    "                \n",
    "\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "            连续子数组k   \n",
    "            贡献法：\n",
    "                新增一位数字所增加的子数组的方案\n",
    "        \"\"\"\n",
    "        pre = 0\n",
    "        n = len(nums)\n",
    "        cnt =[1]+[0]*n\n",
    "        ans =0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre +=x&1\n",
    "            ans += cnt[pre-k] if pre>=k else 0\n",
    "            cnt[pre]+=1\n",
    "        return ans    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        self.nums = nums\n",
    "        self.n = len(nums)\n",
    "        return self.atMostK(k) - self.atMostK(k - 1)\n",
    "\n",
    "    def atMostK(self, k):\n",
    "        res = 0\n",
    "        left = 0\n",
    "        count = 0\n",
    "        for i in range(self.n):\n",
    "            num = self.nums[i]\n",
    "            count += num & 1\n",
    "            while count > k:\n",
    "                left_num = self.nums[left]\n",
    "                count -= left_num & 1\n",
    "                left += 1\n",
    "            res += i - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        odd = [-1]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 1:\n",
    "                odd.append(i)\n",
    "        odd.append(n)\n",
    "        print(odd)\n",
    "        for i in range(1, len(odd) - k):\n",
    "            ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        presum_dict = defaultdict(int)\n",
    "        presum_dict[0] = 1\n",
    "        res, cur_odd_num = 0, 0\n",
    "        for num in nums:\n",
    "            if num % 2 == 1:\n",
    "                cur_odd_num += 1\n",
    "            presum_dict[cur_odd_num] +=1\n",
    "            if cur_odd_num - k in presum_dict.keys():\n",
    "                res += presum_dict[cur_odd_num - k]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        a = 0\n",
    "        n = len(nums)\n",
    "        table = Counter()\n",
    "        table[0]+=1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a += (nums[i]%2)\n",
    "            table[a] += 1\n",
    "            if a-k in table:\n",
    "                ans += table[a-k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        # 奇数数量前缀和\n",
    "        c = Counter(accumulate((n & 1 for n in nums), initial=0))\n",
    "        return sum(c[n - k] * v for n, v in c.items())\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dic = collections.defaultdict(int)\n",
    "        dic[0] = 1\n",
    "        cnt = ans = 0\n",
    "        for i in range(n):\n",
    "            cnt += nums[i] % 2\n",
    "            ans += dic[cnt-k]\n",
    "            dic[cnt] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和不仅指代前几个元素和，也可以指代前几个奇数元素个数和\n",
    "        count = 0\n",
    "        pre = 0 # 前缀和,计算前面的奇数元素个数\n",
    "        mp = dict()\n",
    "        mp[0] = 1 # 单个非空元素也算子数组，所以必须把空数组的奇数元素个数也算进去\n",
    "        for i in range(len(nums)):\n",
    "            pre += (nums[i] % 2) # 是否为奇数，是为1，否为0\n",
    "            if pre not in mp:\n",
    "                mp[pre] = 0\n",
    "            if pre-k not in mp:\n",
    "                mp[pre-k] = 0\n",
    "            count += mp[pre-k]\n",
    "            mp[pre] += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        counts = defaultdict(int)\n",
    "        res, cur = 0, 0\n",
    "        counts[0] = 1\n",
    "        for num in nums:\n",
    "            if num % 2 == 1:\n",
    "                cur += 1\n",
    "            res += counts[cur - k]\n",
    "            counts[cur] += 1\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
